home *** CD-ROM | disk | FTP | other *** search
/ Chip 1997 May / CHIP Mayıs 1997.iso / qtools / qbsp / portals.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-12  |  11.2 KB  |  577 lines
  1.  
  2. #include "bsp5.h"
  3.  
  4.  
  5. node_t    outside_node;        // portals outside the world face this
  6.  
  7. //=============================================================================
  8.  
  9. /*
  10. =============
  11. AddPortalToNodes
  12. =============
  13. */
  14. void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
  15. {
  16.     if (p->nodes[0] || p->nodes[1])
  17.         Error ("AddPortalToNode: allready included");
  18.  
  19.     p->nodes[0] = front;
  20.     p->next[0] = front->portals;
  21.     front->portals = p;
  22.     
  23.     p->nodes[1] = back;
  24.     p->next[1] = back->portals;
  25.     back->portals = p;
  26. }
  27.  
  28.  
  29. /*
  30. =============
  31. RemovePortalFromNode
  32. =============
  33. */
  34. void RemovePortalFromNode (portal_t *portal, node_t *l)
  35. {
  36.     portal_t    **pp, *t;
  37.     
  38. // remove reference to the current portal
  39.     pp = &l->portals;
  40.     while (1)
  41.     {
  42.         t = *pp;
  43.         if (!t)
  44.             Error ("RemovePortalFromNode: portal not in leaf");    
  45.  
  46.         if ( t == portal )
  47.             break;
  48.  
  49.         if (t->nodes[0] == l)
  50.             pp = &t->next[0];
  51.         else if (t->nodes[1] == l)
  52.             pp = &t->next[1];
  53.         else
  54.             Error ("RemovePortalFromNode: portal not bounding leaf");
  55.     }
  56.     
  57.     if (portal->nodes[0] == l)
  58.     {
  59.         *pp = portal->next[0];
  60.         portal->nodes[0] = NULL;
  61.     }
  62.     else if (portal->nodes[1] == l)
  63.     {
  64.         *pp = portal->next[1];    
  65.         portal->nodes[1] = NULL;
  66.     }
  67. }
  68.  
  69. //============================================================================
  70.  
  71. void PrintPortal (portal_t *p)
  72. {
  73.     int            i;
  74.     winding_t    *w;
  75.     
  76.     w = p->winding;
  77.     for (i=0 ; i<w->numpoints ; i++)
  78.         printf ("(%5.0f,%5.0f,%5.0f)\n",w->points[i][0]
  79.         , w->points[i][1], w->points[i][2]);
  80. }
  81.  
  82. /*
  83. ================
  84. MakeHeadnodePortals
  85.  
  86. The created portals will face the global outside_node
  87. ================
  88. */
  89. void MakeHeadnodePortals (node_t *node)
  90. {
  91.     vec3_t        bounds[2];
  92.     int            i, j, n;
  93.     portal_t    *p, *portals[6];
  94.     plane_t        bplanes[6], *pl;
  95.     int            side;
  96.     
  97.     Draw_ClearWindow ();
  98.     
  99. // pad with some space so there will never be null volume leafs
  100.     for (i=0 ; i<3 ; i++)
  101.     {
  102.         bounds[0][i] = brushset->mins[i] - SIDESPACE;
  103.         bounds[1][i] = brushset->maxs[i] + SIDESPACE;
  104.     }
  105.     
  106.     outside_node.contents = CONTENTS_SOLID;
  107.     outside_node.portals = NULL;
  108.  
  109.     for (i=0 ; i<3 ; i++)
  110.         for (j=0 ; j<2 ; j++)
  111.         {
  112.             n = j*3 + i;
  113.  
  114.             p = AllocPortal ();
  115.             portals[n] = p;
  116.             
  117.             pl = &bplanes[n];
  118.             memset (pl, 0, sizeof(*pl));
  119.             if (j)
  120.             {
  121.                 pl->normal[i] = -1;
  122.                 pl->dist = -bounds[j][i];
  123.             }
  124.             else
  125.             {
  126.                 pl->normal[i] = 1;
  127.                 pl->dist = bounds[j][i];
  128.             }
  129.             p->planenum = FindPlane (pl, &side);
  130.     
  131.             p->winding = BaseWindingForPlane (pl);
  132.             if (side)
  133.                 AddPortalToNodes (p, &outside_node, node);
  134.             else
  135.                 AddPortalToNodes (p, node, &outside_node);
  136.         }
  137.         
  138. // clip the basewindings by all the other planes
  139.     for (i=0 ; i<6 ; i++)
  140.     {
  141.         for (j=0 ; j<6 ; j++)
  142.         {
  143.             if (j == i)
  144.                 continue;
  145.             portals[i]->winding = ClipWinding (portals[i]->winding, &bplanes[j], true);
  146.         }
  147.     }
  148. }
  149.  
  150. //============================================================================
  151.  
  152. void CheckWindingInNode (winding_t *w, node_t *node)
  153. {
  154.     int        i, j;
  155.     
  156.     for (i=0 ; i<w->numpoints ; i++)
  157.     {
  158.         for (j=0 ; j<3 ; j++)
  159.             if (w->points[i][j] < node->mins[j] - 1
  160.             || w->points[i][j] > node->maxs[j] + 1)
  161.             {
  162.                 printf ("WARNING: CheckWindingInNode: outside\n");
  163.                 return;
  164.             }
  165.     }
  166. }
  167.  
  168. void CheckWindingArea (winding_t *w)
  169. {
  170.     int        i;
  171.     float    total, add;
  172.     vec3_t    v1, v2, cross;
  173.     
  174.     total = 0;
  175.     for (i=1 ; i<w->numpoints ; i++)
  176.     {
  177.         VectorSubtract (w->points[i], w->points[0], v1);
  178.         VectorSubtract (w->points[i+1], w->points[0], v2);
  179.         CrossProduct (v1, v2, cross);
  180.         add = VectorLength (cross);
  181.         total += add*0.5;
  182.     }
  183.     if (total < 16)
  184.         printf ("WARNING: winding area %f\n", total);
  185. }
  186.  
  187.  
  188. void PlaneFromWinding (winding_t *w, plane_t *plane)
  189. {
  190.     vec3_t        v1, v2;
  191.  
  192. // calc plane
  193.     VectorSubtract (w->points[2], w->points[1], v1);
  194.     VectorSubtract (w->points[0], w->points[1], v2);
  195.     CrossProduct (v2, v1, plane->normal);
  196.     VectorNormalize (plane->normal);
  197.     plane->dist = DotProduct (w->points[0], plane->normal);
  198. }
  199.  
  200. void CheckLeafPortalConsistancy (node_t *node)
  201. {
  202.     int            side, side2;
  203.     portal_t    *p, *p2;
  204.     plane_t        plane, plane2;
  205.     int            i;
  206.     winding_t    *w;
  207.     float        dist;
  208.  
  209.     side = side2 = 0;        // quiet compiler warning
  210.  
  211.     for (p = node->portals ; p ; p = p->next[side])    
  212.     {
  213.         if (p->nodes[0] == node)
  214.             side = 0;
  215.         else if (p->nodes[1] == node)
  216.             side = 1;
  217.         else
  218.             Error ("CutNodePortals_r: mislinked portal");
  219.         CheckWindingInNode (p->winding, node);
  220.         CheckWindingArea (p->winding);
  221.  
  222.     // check that the side orders are correct
  223.         plane = planes[p->planenum];
  224.          PlaneFromWinding (p->winding, &plane2);
  225.         
  226.         for (p2 = node->portals ; p2 ; p2 = p2->next[side2])    
  227.         {
  228.             if (p2->nodes[0] == node)
  229.                 side2 = 0;
  230.             else if (p2->nodes[1] == node)
  231.                 side2 = 1;
  232.             else
  233.                 Error ("CutNodePortals_r: mislinked portal");
  234.             w = p2->winding;
  235.             for (i=0 ; i<w->numpoints ; i++)
  236.             {
  237.                 dist = DotProduct (w->points[i], plane.normal) - plane.dist;
  238.                 if ( (side == 0 && dist < -1) || (side == 1 && dist > 1) )
  239.                 {
  240.                     printf ("WARNING: portal siding direction is wrong\n");
  241.                     return;
  242.                 }
  243.             }
  244.             
  245.         }
  246.     }
  247. }
  248.  
  249.  
  250. /*
  251. ================
  252. CutNodePortals_r
  253.  
  254. ================
  255. */
  256. void CutNodePortals_r (node_t *node)
  257. {
  258.     plane_t     *plane, clipplane;
  259.     node_t        *f, *b, *other_node;
  260.     portal_t    *p, *new_portal, *next_portal;
  261.     winding_t    *w, *frontwinding, *backwinding;
  262.     int            side;
  263.  
  264. //    CheckLeafPortalConsistancy (node);
  265.  
  266. //
  267. // seperate the portals on node into it's children    
  268. //
  269.     if (node->contents)
  270.     {
  271.         return;            // at a leaf, no more dividing
  272.     }
  273.  
  274.     plane = &planes[node->planenum];
  275.  
  276.     f = node->children[0];
  277.     b = node->children[1];
  278.  
  279. //
  280. // create the new portal by taking the full plane winding for the cutting plane
  281. // and clipping it by all of the planes from the other portals
  282. //
  283.     new_portal = AllocPortal ();
  284.     new_portal->planenum = node->planenum;
  285.     
  286.     w = BaseWindingForPlane (&planes[node->planenum]);
  287.     side = 0;    // shut up compiler warning
  288.     for (p = node->portals ; p ; p = p->next[side])    
  289.     {
  290.         clipplane = planes[p->planenum];
  291.         if (p->nodes[0] == node)
  292.             side = 0;
  293.         else if (p->nodes[1] == node)
  294.         {
  295.             clipplane.dist = -clipplane.dist;
  296.             VectorSubtract (vec3_origin, clipplane.normal, clipplane.normal);
  297.             side = 1;
  298.         }
  299.         else
  300.             Error ("CutNodePortals_r: mislinked portal");
  301.  
  302.         w = ClipWinding (w, &clipplane, true);
  303.         if (!w)
  304.         {
  305.             printf ("WARNING: CutNodePortals_r:new portal was clipped away\n");
  306.             break;
  307.         }
  308.     }
  309.     
  310.     if (w)
  311.     {
  312.     // if the plane was not clipped on all sides, there was an error
  313.         new_portal->winding = w;    
  314.         AddPortalToNodes (new_portal, f, b);
  315.     }
  316.  
  317. //
  318. // partition the portals
  319. //
  320.     for (p = node->portals ; p ; p = next_portal)    
  321.     {
  322.         if (p->nodes[0] == node)
  323.             side = 0;
  324.         else if (p->nodes[1] == node)
  325.             side = 1;
  326.         else
  327.             Error ("CutNodePortals_r: mislinked portal");
  328.         next_portal = p->next[side];
  329.  
  330.         other_node = p->nodes[!side];
  331.         RemovePortalFromNode (p, p->nodes[0]);
  332.         RemovePortalFromNode (p, p->nodes[1]);
  333.  
  334. //
  335. // cut the portal into two portals, one on each side of the cut plane
  336. //
  337.         DivideWinding (p->winding, plane, &frontwinding, &backwinding);
  338.         
  339.         if (!frontwinding)
  340.         {
  341.             if (side == 0)
  342.                 AddPortalToNodes (p, b, other_node);
  343.             else
  344.                 AddPortalToNodes (p, other_node, b);
  345.             continue;
  346.         }
  347.         if (!backwinding)
  348.         {
  349.             if (side == 0)
  350.                 AddPortalToNodes (p, f, other_node);
  351.             else
  352.                 AddPortalToNodes (p, other_node, f);
  353.             continue;
  354.         }
  355.         
  356.     // the winding is split
  357.         new_portal = AllocPortal ();
  358.         *new_portal = *p;
  359.         new_portal->winding = backwinding;
  360.         FreeWinding (p->winding);
  361.         p->winding = frontwinding;
  362.  
  363.         if (side == 0)
  364.         {
  365.             AddPortalToNodes (p, f, other_node);
  366.             AddPortalToNodes (new_portal, b, other_node);
  367.         }
  368.         else
  369.         {
  370.             AddPortalToNodes (p, other_node, f);
  371.             AddPortalToNodes (new_portal, other_node, b);
  372.         }
  373.     }
  374.     
  375. DrawLeaf (f,1);
  376. DrawLeaf (b,2);    
  377.  
  378.     CutNodePortals_r (f);    
  379.     CutNodePortals_r (b);    
  380.  
  381. }
  382.  
  383.  
  384. /*
  385. ==================
  386. PortalizeWorld
  387.  
  388. Builds the exact polyhedrons for the nodes and leafs
  389. ==================
  390. */
  391. void PortalizeWorld (node_t *headnode)
  392. {
  393.     qprintf ("----- portalize ----\n");
  394.  
  395.     MakeHeadnodePortals (headnode);
  396.     CutNodePortals_r (headnode);    
  397. }
  398.  
  399.  
  400. /*
  401. ==================
  402. FreeAllPortals
  403.  
  404. ==================
  405. */
  406. void FreeAllPortals (node_t *node)
  407. {
  408.     portal_t    *p, *nextp;
  409.     
  410.     if (!node->contents)
  411.     {
  412.         FreeAllPortals (node->children[0]);
  413.         FreeAllPortals (node->children[1]);
  414.     }
  415.     
  416.     for (p=node->portals ; p ; p=nextp)
  417.     {
  418.         if (p->nodes[0] == node)
  419.             nextp = p->next[0];
  420.         else
  421.             nextp = p->next[1];
  422.         RemovePortalFromNode (p, p->nodes[0]);
  423.         RemovePortalFromNode (p, p->nodes[1]);
  424.         FreeWinding (p->winding);
  425.         FreePortal (p);
  426.     }
  427. }
  428.  
  429. /*
  430. ==============================================================================
  431.  
  432. PORTAL FILE GENERATION
  433.  
  434. ==============================================================================
  435. */
  436.  
  437. #define    PORTALFILE    "PRT1"
  438.  
  439. FILE    *pf;
  440. int        num_visleafs;                // leafs the player can be in
  441. int        num_visportals;
  442.  
  443. void WriteFloat (FILE *f, vec_t v)
  444. {
  445.     if ( fabs(v - Q_rint(v)) < 0.001 )
  446.         fprintf (f,"%i ",(int)Q_rint(v));
  447.     else
  448.         fprintf (f,"%f ",v);
  449. }
  450.  
  451. void WritePortalFile_r (node_t *node)
  452. {
  453.     int        i;    
  454.     portal_t    *p;
  455.     winding_t    *w;
  456.     plane_t        *pl, plane2;
  457.  
  458.     if (!node->contents)
  459.     {
  460.         WritePortalFile_r (node->children[0]);
  461.         WritePortalFile_r (node->children[1]);
  462.         return;
  463.     }
  464.     
  465.     if (node->contents == CONTENTS_SOLID)
  466.         return;
  467.  
  468.     for (p = node->portals ; p ; )
  469.     {
  470.         w = p->winding;
  471.         if (w && p->nodes[0] == node
  472.         && p->nodes[0]->contents == p->nodes[1]->contents)
  473.         {
  474.         // write out to the file
  475.         
  476.         // sometimes planes get turned around when they are very near
  477.         // the changeover point between different axis.  interpret the
  478.         // plane the same way vis will, and flip the side orders if needed
  479.             pl = &planes[p->planenum];
  480.             PlaneFromWinding (w, &plane2);
  481.             if ( DotProduct (pl->normal, plane2.normal) < 0.99 )
  482.             {    // backwards...
  483.                 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[1]->visleafnum, p->nodes[0]->visleafnum);
  484.             }
  485.             else
  486.                 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[0]->visleafnum, p->nodes[1]->visleafnum);
  487.             for (i=0 ; i<w->numpoints ; i++)
  488.             {
  489.                 fprintf (pf,"(");
  490.                 WriteFloat (pf, w->points[i][0]);
  491.                 WriteFloat (pf, w->points[i][1]);
  492.                 WriteFloat (pf, w->points[i][2]);
  493.                 fprintf (pf,") ");
  494.             }
  495.             fprintf (pf,"\n");
  496.         }
  497.         
  498.         if (p->nodes[0] == node)
  499.             p = p->next[0];
  500.         else
  501.             p = p->next[1];
  502.     }
  503.  
  504. }
  505.     
  506. /*
  507. ================
  508. NumberLeafs_r
  509. ================
  510. */
  511. void NumberLeafs_r (node_t *node)
  512. {
  513.     portal_t    *p;
  514.  
  515.     if (!node->contents)
  516.     {    // decision node
  517.         node->visleafnum = -99;
  518.         NumberLeafs_r (node->children[0]);
  519.         NumberLeafs_r (node->children[1]);
  520.         return;
  521.     }
  522.     
  523.     Draw_ClearWindow ();
  524.     DrawLeaf (node, 1);
  525.     
  526.     if (node->contents == CONTENTS_SOLID)
  527.     {    // solid block, viewpoint never inside
  528.         node->visleafnum = -1;
  529.         return;
  530.     }
  531.  
  532.     node->visleafnum = num_visleafs++;
  533.     
  534.     for (p = node->portals ; p ; )
  535.     {
  536.         if (p->nodes[0] == node)        // only write out from first leaf
  537.         {
  538.             if (p->nodes[0]->contents == p->nodes[1]->contents)
  539.                 num_visportals++;
  540.             p = p->next[0];
  541.         }
  542.         else
  543.             p = p->next[1];        
  544.     }
  545.  
  546. }
  547.  
  548.  
  549. /*
  550. ================
  551. WritePortalfile
  552. ================
  553. */
  554. void WritePortalfile (node_t *headnode)
  555. {
  556. // set the visleafnum field in every leaf and count the total number of portals
  557.     num_visleafs = 0;
  558.     num_visportals = 0;
  559.     NumberLeafs_r (headnode);
  560.     
  561. // write the file
  562.     printf ("writing %s\n", portfilename);
  563.     pf = fopen (portfilename, "w");
  564.     if (!pf)
  565.         Error ("Error opening %s", portfilename);
  566.         
  567.     fprintf (pf, "%s\n", PORTALFILE);
  568.     fprintf (pf, "%i\n", num_visleafs);
  569.     fprintf (pf, "%i\n", num_visportals);
  570.     
  571.     WritePortalFile_r (headnode);
  572.     
  573.     fclose (pf);
  574. }
  575.  
  576.  
  577.